package com.wtgroup.demo.mianshi.算法.动态规划.暴力递归;

/**
 * LC 1143
 *
 * "a12bc345def" , "MNP123QRS45Z", 答案: "12345"
 * @author nisus
 * @version 0.1
 * @since 2023/6/2 9:41
 */
public class Q_两个字符串最长公共子序列 {

    public static void main(String[] args) {
        // String str1 = "a12bc345def" , str2 = "MNP123QRS45Z";
        String str1 = "a12bc34def7o9p9" , str2 = "MNP123QRS4Z94";
        String res = D_递归尝试.main(str1, str2);
        System.out.println(res);
    }

    static class D_递归尝试 {
        static String main(String str1, String str2) {

            return func(str1, str2, 0, 0);
        }

        static String func(String str1, String str2, int p1, int p2) {
            if (p1 == str1.length() - 1 || p2 == str2.length() - 1) {
                return str1.charAt(p1) == str2.charAt(p2) ? String.valueOf(str1.charAt(p1)) : "";
            }

            int N1 = str1.length(), N2 = str2.length();
            String ans = "";

            // [p1,p2] 右下方一片区域最大值
            for (int i = p1+1; i < N1; i++) {
                for (int j = p2+1; j < N2; j++) {
                    String oneRes = func(str1, str2, i, j);
                    if (oneRes.length() > ans.length()) {
                        ans = oneRes;
                    }
                }
            }

            // String restRes = func(str1, str2, p1 + 1, p2 + 1);
            if (str1.charAt(p1)  == str2.charAt(p2)) {
                return str1.charAt(p1) + ans;
            } else {
                return ans;
            }
        }
    }


}
